package com.vint.leetcode;

import com.vint.common.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Leetcode655 {
	public List<List<String>> printTree(TreeNode root) {
		List<List<String>>ret = new ArrayList<>();
		if(null == root) return ret;
		if(null==root.left && root.right == null){
			List<String> line = new ArrayList<>();
			line.add(root.val + "");
			ret.add(line);
			return ret;
		}
		//第一行
		List<String> one = new ArrayList<>();
		ret.add(one);


		List<List<String>> tl = printTree(root.left);
		List<List<String>> tr = printTree(root.right);
		int index = 1;
		int width = 0;
		if(tl.size()!=0&&tr.size()!=0){
			width = Math.max(tl.get(tl.size()-1).size(), tr.get(tr.size() - 1).size());
		}
		if (tl.size() == 0) width = tr.get(tr.size()-1).size();
		if (tr.size() == 0) width = tl.get(tl.size()-1).size();
		while(index <= tl.size() || index <= tr.size()) {
			List<String> line = new ArrayList<>();
			if(index > tl.size()){
				List<String> tmp = new ArrayList<>(width);
				Collections.fill(tmp, "");
				line.addAll(tmp);
				line.add("");
				line.addAll(tr.get(index -1));
			} else if(index > tr.size()) {
				List<String> tmp = new ArrayList<>(width);
				Collections.fill(tmp, "");
				line.addAll(tl.get(index -1));
				line.add("");
				line.addAll(tmp);

			} else {
				line.addAll(tl.get(index -1));
				line.add("");
				line.addAll(tr.get(index - 1));
				ret.add(line);
			}
			index++;
		}
		List<String> tmp = new ArrayList<>(width);
		Collections.fill(tmp, "");
		one.addAll(tmp);
		one.add(root.val + "");
		one.addAll(tmp);
		return ret;
	}
}
